Machine Learning Theory CS6783
News :
  1. Welcome to first day of class!
  2. Join ED Discussions Via Canvas

Location and Time :
Location : Hollister Hall, Room 320

Online: The class will also be available via zoom only for Cornell Tech students on request
Time : Tue-Thu 1:25 PM to 2:40 PM (EST)

Office Hours : Wed 2-3pm at 477 CIS Building (new building).

TA: August Chen
Office Hours : Tuesday from 5:30-6:30 at Bowers 464a,
Zoom Link: Link
Description : We will discuss both classical results and recent advances in both statistical (iid batch) and online learning theory. The course aims at providing students with tools and techniques to understand inherent mathematical complexities of learning problems, to analyze and prove performance guarantees for machine learning methods and to develop theoretically sound learning algorithms.

Pre-requisite : Student requires a basic level of mathematical maturity and ease/familiarity with theorems and proofs style material. Familiarity with probability theory, basics of algorithms and an introductory course on Machine Learning (CS 4780 or equivalent) are required. M.Eng. and undergraduate students require permission of instructor.

Grading :
Assignments : There will be a total of 4 assignments covering 40% of your grade.

Term project :
    There will be a term project due by the end of the course. The project is worth 52% of your grade. The project could be your choice of research problem approved by me for which you will submit a report by end of term. In the second week of the course I will also give a list of suggestions for broad topics that students can choose from. Groups of at most 3 students per project.
Paper Reading : There will be a total of 2 paper reading covering 8% of your grade (with quizzes for each one).



Lectures/Schedule :
Date Topic Notes Assignments
8/26/25 Introduction, course details, A Bit of Fun [Lec 1]
[Course Info]
Ref: [1] (ch 2) 		Assignment 0 Out
Not for grade, no submnission
8/28/25 Bit Prediction and Cover's Lemma [Lec 2]
Ref: [1] (ch 2)
9/02/25 NO LECTURE NO LECTURE
9/04/25 Cover's Lemma, Rademacher Complexity and Betting Problem [Lec 3]
Ref: [1] (ch 2) 		Assignment 1 Out
Due 18th Sep, 2025
9/09/25 Linear Betting Game With Covariates Contd., Different Learning Frameworks [Lec 4]
9/11/25 Different Learning Frameworks [Lec 5]
9/16/25 Minimax Rates, ERM and Uniform Convergence [Lec 6]
9/18/25 ERM, Uniform Convergence and Rademacher Complexity [Lec 7] Assignment 1 Due Today
9/23/25 Massart's Finite Lemma, Growth Function and VC Dimension [Lec 8] Assignment 2 Out
Due 7th Oct, 2025
9/25/25 Properties of Rademacher Complexity and Examples [Lec 9]
9/30/25 Rademacher Complexity Contraction Lemms, Applications and Covering Number [Lec 10]
10/02/25 Covering Numbers, Pollard's Bound and Dudley Chaining [Lec 10]
10/07/25 Finishing up Dudley Chaining and Lower Bounds for Statistical Learning [Lec 11] Assignment 2 Due Today
10/09/25 Finishing up Lower Bounds for Statistical Learning and Statistical LEarning Beyond Supervised Learning [Lec 13] Assignment 3 Out
Due 23rd Oct, 2025
10/14/25 FALL BREAK NO LECTURE
10/16/25 Algorithmic Stability to Characterize General Statistical Learnability [Lec 14] Initial Project Idea Proposal Due
10/21/25 Online Convex Optimization and Mirror Descent [Lec 15]
10/23/25 Online Convex Optimization and Mirror Descent [Lec 15]
10/28/25 Mirror Descent With Local Norms, Online Linear Bandits [Lec 16]
10/30/25 Online Linear Bandits [Lec 17] Assignment 4 Out
11/04/25 Stochastic Multiarmed Bandits and UCB Algorithm [Lec 18] Assignment 3 Due today
11/06/25 UCB Algorithm cntd. + Lower Bound [Lec 18] + [Lec 19]
11/11/25 Instance Specific Lower Bound for Stochastic Bandit [Lec 19]
11/13/25 Contextual Bandit [Lec 20]
11/18/25 Assignment 4 Due today
11/20/25
11/25/25
11/27/25 THANKSGIVING BREAK NO LECTURE
12/02/25
12/04/25


Reference Material :

  1. Statistical Learning and Sequential Prediction, A. Rakhlin and K. Sridharan [pdf]

  2. Introduction to Statistical Learning Theory, O. Bousquet, S. Boucheron, and G. Lugosi [pdf]

  3. Prediction Learning and Games, N. Cesa-Bianchi and G. Lugosi [link]

  4. Understanding Machine Learning From Theory to Algorithms, S. Ben David and S. Shalev-Shwartz [link]

  5. Introduction to Online Convex Optimization, Elad Hazan [link]

  6. Concentration inequalities, S. Boucheron, O. Bousquet, and G. Lugosi [pdf]

  7. A Gentle Introduction to Concentration Inequalities, K. Sridharan [pdf]

  8. On the Vapnik-Chervonenkis-Sauer Lemma by Leon Bottou [link]